package 题目集.树.构建树;

import java.util.Scanner;

//https://pintia.cn/problem-sets/1744288973314506752/exam/problems/1744289010547331082?type=7&page=0
public class 完全二叉树后序转层序 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n = sc.nextInt();
        postOrder=new int[n];
        levelOrder=new int[n+1];
        for (int i = 0; i < postOrder.length; i++) {
            postOrder[i]=sc.nextInt();
        }
        builder(1);
        StringBuilder sb=new StringBuilder();
        for (int i = 1; i < levelOrder.length; i++) {
            sb.append(levelOrder[i]).append(" ");
        }
        sb.deleteCharAt(sb.length()-1);
        System.out.println(sb.toString());
    }
    static int[] postOrder;
    static int[] levelOrder;
    static int count=0;

    /**
     * 完全二叉树后序遍历转层序遍历
     * @param i:层序遍历中父节点的位置
     */
    public static void builder(int i) {
        int left=i<<1;
        int right=i<<1|1;
        if (left<levelOrder.length){
            builder(left);
        }
        if (right<levelOrder.length){
            builder(right);
        }
        levelOrder[i]=postOrder[count++];
    }
}
